package 算法.练习1;

import java.util.Scanner;

/**
 * @author:谢君臣
 * @Date:2021/8/24-16:52
 * @version:1.0
 * @function:
 */
public class NC92 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        StringBuilder res = new StringBuilder();
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else if (dp[i - 1][j] > dp[i][j - 1])
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = dp[i][j - 1];
            }
        }
        int i = str1.length(),j = str2.length();
        for (int n = dp[str1.length()][str2.length()]; n>0 ; n--) {
            while (dp[i][j-1]==n)j--;
            while (dp[i-1][j]==n)i--;
            res.append(str1.charAt(i-1));
            i--;
            j--;
        }
        System.out.println(res.reverse().toString());
    }
    public static String LCS(String s1, String s2) {
        int row = s1.length();
        int column = s2.length();
        int[][] dp = new int[row + 1][column + 1];
        for (int i = 1; i < row + 1; i++) {
            for (int j = 1; j < column + 1; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        if(dp[row][column]==0) return "-1";
        char[] lcs = new char[dp[row][column]];
        int cur = lcs.length - 1;
        while (true) {
            if (s1.charAt(row - 1) == s2.charAt(column - 1)) {
                lcs[cur--] = s1.charAt(row - 1);
                if (cur < 0) return new String(lcs);
                row--;
                column--;
            } else {
                if (dp[row - 1][column] > dp[row][column - 1]) {
                    row--;
                } else {
                    column--;
                }
            }
        }
    }
}
